JZ40 数组中只出现一次的两个数

https://www.nowcoder.com/practice/389fc1c3d3be4479a154f63f495abff8

这题就是利用

^ 有两个性质：

0 ^ N = N 和 N ^ N = 0
异或运算满足交换律和结合律

交换律
a ^ b = b ^ a

结合律
a ^ b ^ c = a ^ (b ^ c)

本题就是利用的

a^b^a = a^a^b = b^a^a =b

其他数字都出现了两次，找出该数字。思路就是遍历数组，对每一个数字都求异或，最后得到的值就是要找的数字。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] FindNumsAppearOnce (int[] array) {
        // 创建一个变量
        int eor = 0;
        // 遍历这个数组，令它从头异或到尾
        for(int cur : array) {
            eor ^= cur;
        }

        // ~eor 表示它的每一位取反
        // ~eor + 1 就是求补码
        // 所以这种 & 补码的操作其实就是快速的找到从右边开始第一个 1 的位置
        int rightOne = eor & (~eor + 1);
    
        // 此时 eor 就是两个只出现一次的数的 a^b 所以丢回去再算一次
        int e2 = 0;
        for (int j : array) {
            if ((j & rightOne) != 0) {
                e2 ^= j;
            }
        }

        int a = e2;
        int b = eor ^ e2;

        return a < b ? new int[]{a,b} : new int[]{b,a};
    }
}